package com.leetcode.partition8;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/5 10:45
 */
public class LC763划分字母区间 {

    public static List<Integer> partitionLabels(String s) {
        return hashTable(s.toCharArray());
    }

    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }

    private static List<Integer> hashTable(final char[] words) {
        final int[] hashTable = new int[27];          //哈希表记录对应字符的最后一次出现的索引
        for (int i = 0; i < words.length; i++) {
            hashTable[words[i] - 'a'] = i;
        }
        List<Integer> answers = new ArrayList<>();
        int left = 0, right = 0;
        for (int i = 0; i < words.length; i++) {
            right = Math.max(right, hashTable[words[i] - 'a']);         //当前字符最后一次出现的索引
            if (right == i) {
                answers.add(right - left + 1);
                left = right + 1;
            }
        }
        return answers;
    }
}
